#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
#include <math.h>
#include <limits.h>
#define LOCAL_TEST 1
#define M 0


int cnr(int n, int r){
	int ans[M], i, j;
	if(r>n/2) r = n-r;
	memset(ans, 0, sizeof(ans));
	for(ans[n]=1, i=0; i<=r; ++i){
		for(j=n-1; j>=i; --j) ans[j] += ans[j+1];
	}
	return ans[r];
	return 1;
}
/*
 * 		+-  1 n=0,1
 * 		|
 * n! = +	n*(n-1)! n is odd
 * 		|
 * 		+-	c(n,n/2)*((n/2)!)^2 n is even
 */
int fact1(int n){
	if(n==0 || n==1) return 1;
	if(n%2) return n * fact1(n-1);
	else {
		int x = fact1(n/2);
		return x*x*cnr(n, n/2);
	}
}


static void solve(void){
}

#if LOCAL_TEST
void run(void){
		solve();
}
#endif
